class Solution 
{
private:
    // 存储有向图的邻接表，edges[u]包含u的所有后继课程（即修完u才能修的课程）
    vector<vector<int>> edges;
    // 记录每个节点的状态：0=未访问，1=访问中（递归栈中），2=已访问完成
    vector<int> visited;
    // 存储拓扑排序结果，按完成时间倒序排列，最后需要反转得到正确顺序
    vector<int> result;
    // 标记是否存在环，初始为true，检测到环则设为false
    bool valid = true;


public:
    // 深度优先搜索遍历图，检测环并构建拓扑排序
    void dfs(int u) 
    {
        visited[u] = 1; // 标记当前节点为访问中
        // 遍历所有后继节点
        for (int v : edges[u]) 
        {
            if (visited[v] == 0) { // 遇到未访问的节点，继续递归
                dfs(v);
                if (!valid) return; // 发现环则立即返回
            }
            else if (visited[v] == 1) { // 后继节点在递归栈中，说明存在环
                valid = false;
                return;
            }
            // 若visited[v]==2，说明该节点已处理完毕，无需操作
        }
        visited[u] = 2; // 当前节点处理完毕
        result.push_back(u); // 按完成顺序加入结果（后续再反转）
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        edges.resize(numCourses); // 初始化邻接表
        visited.resize(numCourses); // 初始化访问状态数组
        // 构建图，prerequisites中的每个依赖对[ai, bi]表示bi是ai的前置课程
        for (const auto& info : prerequisites) 
        {
            edges[info[1]].push_back(info[0]); // 添加边bi -> ai
        }
        // 遍历所有节点，确保非连通图也能被处理
        for (int i = 0; i < numCourses && valid; ++i) 
        {
            if (!visited[i])  // 遇到未访问的节点，开始DFS
            {
                dfs(i);
            }
        }
        if (!valid)  // 存在环，返回空数组
        {
            return {};
        }
        // 反转结果，得到拓扑排序的正确顺序
        reverse(result.begin(), result.end());
        return result;
    }
};